|
In mathematics, the Gabriel graph of a set ''S'' of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set ''S'' in which any points ''P'' and ''Q'' in ''S'' are adjacent precisely if they are distinct and the closed disc of which line segment ''PQ'' is a diameter contains no other elements of ''S''. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. R. Gabriel, who introduced them in a paper with R. R. Sokal in 1969. The Gabriel graph is a subgraph of the Delaunay triangulation; it can be found in linear time if the Delaunay triangulation is given . The Gabriel graph contains as a subgraph the Euclidean minimum spanning tree, the relative neighborhood graph, and the nearest neighbor graph. It is an instance of a beta-skeleton. Like beta-skeletons, and unlike Delaunay triangulations, it is not a geometric spanner: for some point sets, distances within the Gabriel graph can be much larger than the Euclidean distances between points . A finite site percolation threshold for Gabriel graphs has been proven to exist by , and more precise values of both site and bond thresholds have been given by . == References == *. *. *. *. *. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Gabriel graph」の詳細全文を読む スポンサード リンク
|